﻿namespace JoinBox.Basal;

public static class Sort
{
    // https://www.runoob.com/w3cnote/quick-sort.html
    /// <summary>
    /// 快速排序,整形
    /// </summary>
    /// <param name="arr">数组</param>
    /// <param name="begin">开始</param>
    /// <param name="end">结束</param>
    public static void QuickSort(int[] arr, int begin, int end)
    {
        if (begin < end)
        {
            // Swap(s[l], s[(l + r) / 2]); // 有的书上是以中间的数作为基准数的,要实现这个方便非常方便,直接将中间的数和第一个数进行交换就可以了。
            int i = begin, j = end, x = arr[begin];
            while (i < j)
            {
                while (i < j && arr[j] >= x) // 从右向左找第一个小于x的数
                    j--;
                if (i < j)
                    arr[i++] = arr[j];

                while (i < j && arr[i] < x) // 从左向右找第一个大于等于x的数
                    i++;
                if (i < j)
                    arr[j--] = arr[i];
            }
            arr[i] = x;
            QuickSort(arr, begin, i - 1); // 递归调用
            QuickSort(arr, i + 1, end);
        }
    }

    /// <summary>
    /// 快速排序,字符串
    /// </summary>
    /// <param name="arr">需要排序的字符串数组</param>
    /// <param name="begin">排序元素的起始下标</param>
    /// <param name="end">排序元素的结止下标</param>
    public static void QuickSort(string[] arr, int begin, int end)
    {
        // 有可能造成 start>end
        // 因为递归调用时j+1,可能引起j比end还大1。
        // 另外如果数组是空的,或者输入错误也会出现这种情况
        if (begin >= end)
            return;   // 两个指针重合就返回,结束调用

        // 取中间元素为中心点,然后移到最右边
        int sign = (begin + end) / 2;
#pragma warning disable IDE0180 // 使用元组交换值
        string tmp = arr[end];
        arr[end] = arr[sign];
        arr[sign] = tmp;
#pragma warning restore IDE0180 // 使用元组交换值
        int j = begin;

        for (int i = begin; i <= end - 1; i++)
        {
            // 小于的元素和标记互换,等于的不能互换,否则会形成死循环
            if (arr[i].CompareTo(arr[end]) == -1)
            {
                tmp    = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                j++;
            }
        }

        // 把标记元素和第一个>=它的元素位置互换,这样数组就分成2个部分,一个部分比中心值小,一个部分比中心值大。
        tmp = arr[j];
        arr[j] = arr[end];
        arr[end] = tmp;
        QuickSort(arr, begin, j);
        QuickSort(arr, j + 1, end);
    }
}


#if true2
    // 这个例子是错误的,它非常慢
    public static void QuickSort2(int[] arr, int begin, int end)
    {
        if (begin < end)
        {
            int x = arr[begin];
            int i = begin;
            int j = end;
            while (true && i < j)
            {
                while (true && i < j)
                {
                    if (arr[j] <= x)
                    {
                        arr[i] = arr[j];
                        break;
                    }
                    else
                    {
                        j--;
                    }
                }
                while (true && i < j)
                {
                    if (arr[i] > x)
                    {
                        arr[j] = arr[i];
                        break;
                    }// if结束
                    else
                    {
                        i++;
                    }
                }// while结束
            }    // 第一个While结束

            // 跳出循环,现在i==j了,i是中间位。
            arr[i] = x;
            QuickSort2(arr, begin, i - 1);
            QuickSort2(arr, i + 1, end);
        }
    }
#endif